// 第 N 个太波那契数
public class Code1 {
    public int tribonacci(int n) {
        // 1、创建一个 dp 表
        // 2、初始化
        // 3、填表
        // 4、返回值

        // 处理边界情况
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        // 需要一个 n+1 规模的 dp 表
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = dp[2] = 1;

        for(int i=3;i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
}
